package com.algrithom.tree.binarytree;

import java.util.Arrays;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 1676. 二叉树的最近公共祖先 IV
 * 
 * @author think
 */
public class Solution4 {
    
    public static void main(String[] args){
        TreeNode<Integer> root = TreeOperUtil.createTree(Arrays.asList(3,5,1,6,2,0,8,null,null,7,4).toArray(new Integer[]{}),0);
        Solution4 solution4 = new Solution4();
        TreeNode<Integer>[] nodes = new TreeNode[]{new TreeNode<>(4),new TreeNode<>(7)};
        TreeNode<Integer> result = solution4.lowestCommonAncestor(root,nodes);
        System.out.println(result.getValue());
    }
    
    public TreeNode<Integer> lowestCommonAncestor(TreeNode<Integer> root,TreeNode<Integer>[] nodes){
        if (root == null) {
            return null;
        }
        
        if (isIn(nodes,root)) {
            return root;
        } else {
            TreeNode<Integer> res;
            TreeNode<Integer> left = lowestCommonAncestor(root.getLeftChild(),nodes);
            TreeNode<Integer> right = lowestCommonAncestor(root.getRightChild(),nodes);
            if (left != null && right != null) {
                return root;
            }
            res = (left == null) ? right : left;
            return res;
        }
        
    }
    
    public boolean isIn(TreeNode<Integer>[] nodes,TreeNode<Integer> root){
        for (TreeNode<Integer> node : nodes) {
            if (node == root) {
                return true;
            }
        }
        return false;
    }
}
